package String.easy;

import jdk.nashorn.internal.runtime.regexp.RegExp;

import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 *      说明：本题中，我们将空字符串定义为有效的回文串。
 *
 * 2. 算法分析
 *      1. 算法一：
 *          首先我们定义一个RemoveOtherInString()将字符串中的非数字或者非字母的字符去掉一次遍历时间复杂度为O(n)
 *          为此我们还需要一个额外的辅助函数isPalindrome()判断当前字符是否为数字或者字母时间复杂度为O(1)
 *          最后我们的思路就是将字符串中的非字母和数字的去掉。在通过双指针判断当前纯字符字符串是否回文，时间复杂度为
 *          O(n)
 *          此算法的时间复杂度比较高，leetcode上的测试结果为 击败了全国5.23%，空间复杂度击败了16.29%。说明还有更
 *          好的算法实现，上述代码过于复杂，写了两个辅助函数，才实现上述问题的求解
 *
 *      2. 算法二：
 *          还是利用双指针来判断当前字符串
 *
 *
 *
 * 3. 代码实现
 */

@SuppressWarnings("all")
public class 有效的回文 {
    public static void main(String[] args) {
        System.out.println(isPalindrome2("race a car"));
    }

    public static boolean isPalindrome(String s) {
        String removed = RemoveOtherInString(s);
        if(removed.length() == 0 || removed.length() == 1) {return true;}
        int i = 0;
        int j = removed.length() - 1;
        while(i < j) { // 退出条件 i == j 无论字符串的长度为奇数或者偶数
            if ((removed.charAt(i) + "").equalsIgnoreCase(removed.charAt(j) + "")) {
                i++;
                j--;
            }
        }
        return true;
    }

    // 判断字符是否为数字或者字母，如果是返回true，否则返回false
    public static boolean isAlphanumeric(char ch) {
        if(Character.isLetter(ch) || Character.isDigit(ch)) {return true;}
        return false;
    }

    public static String RemoveOtherInString(String s) {
        StringBuilder builder = new StringBuilder(s);
        for(int i = builder.length() - 1; i >= 0; i--) {
            if(!isAlphanumeric(builder.charAt(i))) {
                builder.delete(i,i+1);
            }
        }
        for(int i = builder.length() - 1; i > 0; i--) {
            if(builder.charAt(i) == ' ') {
                builder.delete(i,i+1);
            }
        }
        return builder.toString();
    }

    /**
     * 双指针   虽然代码结构简化了，但是时间复杂度并没有提高很多，空间复杂度优化了原来的一半
     * @param s
     * @return
     */
    public static boolean isPalindrome2(String s) {
        StringBuilder chs = new StringBuilder();
        for (int i = 0; i < s.length(); i++) { // 一次扫描将所有的字母和数字放置按顺序放置到chs中
            if (Character.isLetter(s.charAt(i)) || Character.isDigit(s.charAt(i))) {
                chs.append(s.charAt(i));
            }
        }
        System.out.println(chs);
        if (chs.length() == 0 || chs.length() == 1) {return true;}

        int i = 0; // 指向s的头部的指针
        int j = chs.length() - 1; // 指向s的尾部的指针
        while (i < j) {
            if (!(chs.charAt(i)+"").equalsIgnoreCase(chs.charAt(j)+"")) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    /**
     *  官方给的一个比较优的解决方式：调用java底层封装好的API
     *  这也再一次说明对java底层的一些关于字符的API需要收悉，能过极大的简化
     *  islower(char c) 是否为小写字母
     *  isupper(char c) 是否为大写字母
     *  isdigit(char c) 是否为数字
     *  isalpha(char c) 是否为字母
     *  isalnum(char c) 是否为字母或者数字
     *  toupper(char c) 字母小转大
     *  tolower(char c) 字母大转小
     *  还有利用正则表达是来解决  主要是我正则不熟悉，最开始的想法就是使用正则表达式，但是正则表达式不会写
     *  s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
     * @param s
     * @return
     */
    public static boolean isPalindrome3(String s) {
        StringBuilder chs = new StringBuilder();
        for (int i = 0; i < s.length(); i++) { // 一次扫描将所有的字母和数字放置按顺序放置到chs中
            if (Character.isLetter(s.charAt(i)) || Character.isDigit(s.charAt(i))) {
                chs.append(s.charAt(i));
            }
        }
        System.out.println(chs);
        if (chs.length() == 0 || chs.length() == 1) {return true;}

        int i = 0; // 指向s的头部的指针
        int j = chs.length() - 1; // 指向s的尾部的指针
        while (i < j) {
            if (!(chs.charAt(i)+"").equalsIgnoreCase(chs.charAt(j)+"")) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

}
